package backtrack;
import java.util.*;
public class _01_77_组合_剪枝 {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {

    	backtracking(n, k, 1);
    	
    	return result;
    }
    
    public void backtracking(int n ,int k ,int startIndex) {
    	
    	if(item.size() == k) {
    		result.add(new ArrayList(item));
    		return;
    	}

    	/*
    	 * 已经选择的元素个数：item.size();
    	 * 所需需要的元素个数为: k - item.size();
    	 * 列表中剩余元素（n-i） >= 所需需要的元素个数（k - item.size()）
    	 * 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历
    	 * */
    	
    	for(int i = startIndex; i <= n - (k-item.size()) + 1; i++) {
    		// 
    		item.add(i);
    		backtracking(n, k, i + 1);
    		item.remove(item.size() - 1);
    	}
    	
    }
	public static void main(String[] args) {
		_01_77_组合_剪枝 a = new _01_77_组合_剪枝();
		a.combine(1, 1);
//		System.out.println();
	}
}
